package com.sgffsg.learn.javalib.thread;

/**
 * @author: lmk
 * @date: 2024/4/8
 * @desc: 合并数组
 */

/*
 * 两个有序数组合并为一个
 * 如{1,1,3} {2,4}合并为{1,1,2,3,4}
 * 要求时间复杂度不高于O(M + N)  (假设两个数组长度分别为M，N)，
 * 空间复杂度也是: O(M + N)
 **/
public class MergeArrayTest {

    public static void main(String[] args) {
        test(new int[]{1, 3, 5}, new int[]{2, 4, 6}, new int[]{1, 2, 3, 4, 5, 6});
        test(new int[]{1, 1, 3}, new int[]{2, 4}, new int[]{1, 1, 2, 3, 4});
        test(new int[]{1}, new int[]{2}, new int[]{1, 2});
        test(new int[]{1}, new int[]{}, new int[]{1});
        test(new int[]{}, new int[]{1}, new int[]{1});

    }


    public static void test(int a[], int b[], int c[]) {
        int r[] = merge(a, b);
        if (r == null || r.length != c.length) {
            throw new IllegalStateException("r == null or inconsistent length error");
        }
        for (int i = 0; i < r.length; i++) {
            if (c[i] != r[i]) {
                throw new IllegalStateException("char inconsistent");
            }
        }
        System.out.println("OK");
    }

    private static int[] merge(int[] a, int[] b) {
        int[] result = new int[a.length + b.length];
        int indexA = 0;
        int indexB = 0;
        int indexNew = 0;
        if (a.length == 0) {
            return b;
        }
        if (b.length == 0) {
            return a;
        }
        while (indexA < a.length || indexB < b.length) {
//            System.out.println("indexA = " + indexA + ", indexB = " + indexB);
            if (indexA == a.length){
                result[indexNew++] = b[indexB];
                indexB++;
            } else if (indexB == b.length){
                result[indexNew++] = a[indexA];
                indexA++;
            } else if (a[indexA]<=b[indexB]){
                result[indexNew++] = a[indexA];
                indexA++;
            } else {
                result[indexNew++] = b[indexB];
                indexB++;
            }


        }
        printArray(result);
        return result;
    }

    private static void printArray(int[] a){
        for (int i = 0; i < a.length; i++){
            System.out.print(a[i]+",");
        }
    }

}
